#include <iostream>

/*
 * TabuSearch.cpp
 *
 *  Created on: Jun 2, 2009
 *      Author: ruslan
 */

#include <list>
#include <stdlib.h>
#include <time.h>

#include "TabuSearch.h"
#include "Search.h"
#include "SearchWithArrays.h"
#include "Lib.h"

using namespace std;
// ===== class TabuSearch =====

TabuSearch::TabuSearch(int weeks, int groupsInWeek, int playersInGroup, long maxIteration=-1)
	:Search(weeks, groupsInWeek, playersInGroup, maxIteration) {
	FAST_SOLUTION_IN_MkSec = -1;
	FAST_SOLUTION_MAX_ITERATION = -1;
	MIN_PLAYER_PENALTY = -1;
	MAX_PLYAER_PENALTY = -1;
	FREQUENCY_FOR_LAST_ITERATIONS = -1;
	CHOOSE_OFTEN_PLYAER_SWAPS = -1;
	mtrxGames = NULL;
	mtrxConflictIndecesLists = NULL;
	mtrx3ConflictIndeces = NULL;
	mtrx4Tabu = NULL;
	minConflicts = -1;
	currConflicts = -1;
	additionalParamsWasSet = false;
	lowFrequencyThreshould = -1;
	MAX_WAITING_OF_PROGRESS = -1;
	MAX_SOFT_PERTURBATIONS = -1;
	START_INIT_ALG = 0;
}

TabuSearch::~TabuSearch() {
	if (mtrxConflictIndecesLists != NULL)
		Lib::deleteMatrix(mtrxConflictIndecesLists, WEEKS);
	if (mtrxGames != NULL)
		Lib::deleteMatrix(mtrxGames, playersCnt);
	if (mtrx4Tabu != NULL) {
		Lib::deleteMatrix4(mtrx4Tabu, WEEKS, playersCnt, playersCnt);
	}
	if (mtrx3ConflictIndeces != NULL)
		Lib::deleteMatrix3(mtrx3ConflictIndeces, WEEKS, GROUPS_IN_WEEK);
}

void TabuSearch::setAdditionalParams(
		int _START_INIT_ALG
		,long _FAST_SOLUTION_MAX_ITERATION
		, int _MIN_PLAYER_PENALTY
		, int _MAX_PLYAER_PENALTY
		, int _MAX_NEIGHBOURS
		, int _TABLE_CHANGE_REGIME
		, int _MAX_WAITING_OF_PROGRESS
		, int _MAX_SOFT_PERTURBATIONS
		, int _FREQUENCY_FOR_LAST_ITERATIONS
		, int _CHOOSE_OFTEN_PLYAER_SWAPS) {

	START_INIT_ALG = _START_INIT_ALG;
	FAST_SOLUTION_MAX_ITERATION = _FAST_SOLUTION_MAX_ITERATION;
	MIN_PLAYER_PENALTY = _MIN_PLAYER_PENALTY;
	MAX_PLYAER_PENALTY = _MAX_PLYAER_PENALTY;
	MAX_NEIGHBOURS = _MAX_NEIGHBOURS;
    TABLE_CHANGE_REGIME = _TABLE_CHANGE_REGIME;
	MAX_WAITING_OF_PROGRESS = _MAX_WAITING_OF_PROGRESS;
	MAX_SOFT_PERTURBATIONS = _MAX_SOFT_PERTURBATIONS;
	FREQUENCY_FOR_LAST_ITERATIONS = _FREQUENCY_FOR_LAST_ITERATIONS;
	CHOOSE_OFTEN_PLYAER_SWAPS = _CHOOSE_OFTEN_PLYAER_SWAPS;

	additionalParamsWasSet = true;
}

void TabuSearch::preInit() {
	if (!additionalParamsWasSet) {
		FAST_SOLUTION_MAX_ITERATION = 1000000;
		MIN_PLAYER_PENALTY = 4;
		MAX_PLYAER_PENALTY = 100;
		MAX_NEIGHBOURS = -1;
	 TABLE_CHANGE_REGIME = 0;
	 MAX_WAITING_OF_PROGRESS = 10;
	 FREQUENCY_FOR_LAST_ITERATIONS = 100;
	 START_INIT_ALG = 0;
	 MAX_SOFT_PERTURBATIONS = 3;
	 CHOOSE_OFTEN_PLYAER_SWAPS = 0;
	}
	FAST_SOLUTION_IN_MkSec = -1;
	lowFrequencyThreshould = 0;

	minConflicts = -1;
	currConflicts = -1;

	mtrxConflictIndecesLists = new list<int>*[WEEKS];
	mtrx3ConflictIndeces = new int**[WEEKS];
	for (int i=0; i<WEEKS; i++) {
		tablesIndecesForNeighboursGeneration.push_back(i);
		mtrxConflictIndecesLists[i] = new list<int>[GROUPS_IN_WEEK];
		mtrx3ConflictIndeces[i] = new int*[GROUPS_IN_WEEK];
		for (int j=0; j<GROUPS_IN_WEEK; j++) {
			mtrxConflictIndecesLists[i][j] = list<int>();
			mtrx3ConflictIndeces[i][j] = new int[PLAYERS_IN_GROUP];
			for (int k=0; k<PLAYERS_IN_GROUP; k++) {
				mtrx3ConflictIndeces[i][j][k] = 0; // there is not conflict in this position
			}
		}
	}

	mtrxGames = new int* [playersCnt];
	for (int i=0; i<playersCnt; i++) {
		mtrxGames[i] = new int [playersCnt];
		for (int j=0; j<playersCnt; j++) {
			if (i==j)
				mtrxGames[i][j] = -1000000; // isn't allowed
			else
				mtrxGames[i][j] = 0;
		}
	}

	mtrx4Tabu = new int***[WEEKS];
	for (int i=0; i<WEEKS; i++) {
		mtrx4Tabu[i] = new int**[playersCnt];
		for (int j=0; j<playersCnt; j++) {
			mtrx4Tabu[i][j] = new int*[playersCnt];
			for (int k=0; k<playersCnt; k++) {
				if (j != k) {
					mtrx4Tabu[i][j][k] = new int[2];
					mtrx4Tabu[i][j][k][0] = 0; // penalty
					mtrx4Tabu[i][j][k][1] = 0; // frequency
				}
				else
					mtrx4Tabu[i][j][k] = NULL;
			}
		}
	}
}

void TabuSearch::getFastSolution() {
	if (START_INIT_ALG == 1) {
		Search* searchWithArrays = new SearchWithArrays(WEEKS, GROUPS_IN_WEEK, PLAYERS_IN_GROUP, FAST_SOLUTION_MAX_ITERATION);
		searchWithArrays->init();
		searchWithArrays->ScheduleIt();
		mtrx3Schedule = searchWithArrays->getCopyOfBestSchedule();
		delete searchWithArrays;
	}
	else
	{
		mtrx3Schedule = new int** [WEEKS];
			for (int i=0; i<WEEKS; i++) {
				mtrx3Schedule[i] = new int* [GROUPS_IN_WEEK];
				for (int j=0; j<GROUPS_IN_WEEK; j++) {
					mtrx3Schedule[i][j] = new int [PLAYERS_IN_GROUP];
					for (int k=0; k<PLAYERS_IN_GROUP; k++) {
						mtrx3Schedule[i][j][k] = -1;
					}
				}
			}
	}

	int maxI = 0;
	for (; maxI<WEEKS && mtrx3Schedule[maxI][GROUPS_IN_WEEK-1][PLAYERS_IN_GROUP-1]>-1; maxI++);
	if (maxI<WEEKS) {
		bool* arrFreePlayersInWeek = new bool[playersCnt];
		Lib::setValueInArr(arrFreePlayersInWeek, playersCnt, true);
		int j=0, k;
		bool exitLoop = false;
		while (j<GROUPS_IN_WEEK && !exitLoop) {
			k=0;
			while (k<PLAYERS_IN_GROUP && !exitLoop) {
				if (mtrx3Schedule[maxI][j][k]>-1) {
					arrFreePlayersInWeek[mtrx3Schedule[maxI][j][k]] = false;
					k++;
				}
				else
					exitLoop = true;
			}
			if (!exitLoop)
				j++;
		}
		int l=0;
		for (; j<GROUPS_IN_WEEK; j++) {
			if (k>=PLAYERS_IN_GROUP)
				k = 0;
			for (; k<PLAYERS_IN_GROUP; k++) {
				for (;l<playersCnt && !arrFreePlayersInWeek[l]; l++);
				mtrx3Schedule[maxI][j][k] = l;
				l++;
			}
		}
		for (int i=maxI+1; i<WEEKS; i++)
			for (int j=0; j<GROUPS_IN_WEEK; j++)
				for (int k=0; k<PLAYERS_IN_GROUP; k++)
					mtrx3Schedule[i][j][k] = j*PLAYERS_IN_GROUP + k;
		delete [] arrFreePlayersInWeek;
	}
}

void TabuSearch::applyFastSolution() {

	// Counts all games for every pairs
	for(int i=0; i<WEEKS; i++)
		for(int j=0; j<GROUPS_IN_WEEK; j++)
			for(int k=1; k<PLAYERS_IN_GROUP; k++)
				for (int l=0; l<k; l++) {
					mtrxGames[mtrx3Schedule[i][j][k]][mtrx3Schedule[i][j][l]]++;
					mtrxGames[mtrx3Schedule[i][j][l]][mtrx3Schedule[i][j][k]]++;
				}

	// Sets conflict positions in schedule according previos operation (counting games for every pair)
	// arrConflictIndeces is not ordered list!
	bool* usedPositions = new bool[PLAYERS_IN_GROUP];
	for(int i=0; i<WEEKS; i++) {
		for(int j=0; j<GROUPS_IN_WEEK; j++) {
			Lib::setValueInArr(usedPositions, PLAYERS_IN_GROUP, false);
			for(int k=1; k<PLAYERS_IN_GROUP; k++) {
				bool kHasConflict = false;
				for (int l=0; l<k; l++) {
					int conflictsTmpCnt = mtrxGames[mtrx3Schedule[i][j][k]][mtrx3Schedule[i][j][l]];
					if (conflictsTmpCnt>1) {
						mtrx3ConflictIndeces[i][j][l]++;
						mtrx3ConflictIndeces[i][j][k]++;
						if (!usedPositions[l]) {
							mtrxConflictIndecesLists[i][j].push_back(l);
							usedPositions[l] = true;
						}
						kHasConflict = true;
					}
				}
				if (kHasConflict) {
					mtrxConflictIndecesLists[i][j].push_back(k);
					usedPositions[k] = true;
				}
			}
		}
	}

	// Counting the conflicts
	currConflicts = 0;
	for (int i=0; i<playersCnt-1; i++)
		for (int j=i+1; j<playersCnt; j++)
			if (mtrxGames[i][j]>1)
				currConflicts += mtrxGames[i][j]-1;

	delete [] usedPositions;
}

void TabuSearch::init() {
	preInit();
	getFastSolution();
	applyFastSolution();
	snapshot();
	wasInit = true;
}

void TabuSearch::GenerateNeighbor2(list<int*>& neighborhoodList, list<int*>& bestNonTabuNeighborhoodList/*don't delete pointrs!*/, list<int*>& bestTabuNeighborhoodList/*don't delete pointrs!*/) {
	int bestNonTabuDelta = 100000;
	int bestTabuDelta = 100000;
	list<int>::iterator iterMtrxConflictIndecesLists;
	int* conflictsCurrPlayerWithConflictPlayerGroup = new int[playersCnt];
	int* JIndecesOfConflictGroups = new int[GROUPS_IN_WEEK]; // indeces of groups where all players has conflicts in the group
	list<int>::iterator iterTablesId = tablesIndecesForNeighboursGeneration.begin();
	bool hotLoopExit = false;
	int neiboursCnt = 0;
	int i; // table's index
	for (; iterTablesId!=tablesIndecesForNeighboursGeneration.end() && !hotLoopExit; iterTablesId++) {
		i=(*iterTablesId);
		Lib::setValueInArr(JIndecesOfConflictGroups, GROUPS_IN_WEEK, -1);// -1 - didn't check, 0 - is not conflict group, 1 - conflict group.
		for (int i2=0; i2<GROUPS_IN_WEEK  && !hotLoopExit; i2++) {
			iterMtrxConflictIndecesLists = mtrxConflictIndecesLists[i][i2].begin();
			int prevJOfConflictPos = -1;
			while ( iterMtrxConflictIndecesLists != mtrxConflictIndecesLists[i][i2].end() && !hotLoopExit ) { // for every error position
				int conflictPosK = (*iterMtrxConflictIndecesLists);

				for (int j=0; j<GROUPS_IN_WEEK && !hotLoopExit; j++) {
					if (i2 == j) continue;
					if (i2<j && JIndecesOfConflictGroups[j] == 1)
						continue;

					// count the count of games with group to reduce calcuations
					int conflictsCurrConflictPlayerWithCurrentGroup = 0;
					int conflictPlayersTmp = 0;
					int curConflictPlayer = mtrx3Schedule[i][i2][conflictPosK]; // Current conflict player
					for (int kk=0; kk<PLAYERS_IN_GROUP; kk++) {
						if (mtrxGames[curConflictPlayer][mtrx3Schedule[i][j][kk]]>0)
							conflictsCurrConflictPlayerWithCurrentGroup++;
						if (mtrx3ConflictIndeces[i][j][kk] > 0)
							conflictPlayersTmp++;
					}

					JIndecesOfConflictGroups[j] = (conflictPlayersTmp >= PLAYERS_IN_GROUP)?1:0;

					if (i2>j || (i2<j && conflictPlayersTmp < PLAYERS_IN_GROUP) ) {
						for (int k=0; k<PLAYERS_IN_GROUP && !hotLoopExit; k++) {
							if (i2<j && mtrx3ConflictIndeces[i][j][k]>0) continue;
							int curPlayer2 = mtrx3Schedule[i][j][k];
							if (i2 != prevJOfConflictPos) {
								conflictsCurrPlayerWithConflictPlayerGroup[curPlayer2] = 0;
								for (int kk=0; kk<PLAYERS_IN_GROUP; kk++) {
									if (mtrxGames[curPlayer2][mtrx3Schedule[i][i2][kk]] > 0)
										conflictsCurrPlayerWithConflictPlayerGroup[curPlayer2]++;
								}
							}

							int delta = conflictsCurrConflictPlayerWithCurrentGroup + conflictsCurrPlayerWithConflictPlayerGroup[curPlayer2]
								- 2*((mtrxGames[curConflictPlayer][curPlayer2]>0)?1:0)
								- mtrx3ConflictIndeces[i][i2][conflictPosK]
								- mtrx3ConflictIndeces[i][j][k];
							int* neighbour = new int[6];
							neighbour[0] = i; // week index
							neighbour[1] = i2;
							neighbour[2] = conflictPosK;
							neighbour[3] = j;
							neighbour[4] = k;
							neighbour[5] = delta;
							neighborhoodList.push_back(neighbour);

							if (mtrx4Tabu[i][curConflictPlayer][curPlayer2][0] <= currIteration) {
								if (delta == bestNonTabuDelta)
									bestNonTabuNeighborhoodList.push_back(neighbour);
								else if (delta < bestNonTabuDelta) {
									bestNonTabuNeighborhoodList.clear();
									bestNonTabuNeighborhoodList.push_back(neighbour);
									bestNonTabuDelta = delta;
									if (delta == -2*(PLAYERS_IN_GROUP-1) )
										hotLoopExit = true;
								}
							}
							else {
								if (delta == bestTabuDelta)
									bestTabuNeighborhoodList.push_back(neighbour);
								else if (delta < bestTabuDelta) {
									bestTabuNeighborhoodList.clear();
									bestTabuNeighborhoodList.push_back(neighbour);
									bestTabuDelta = delta;
								}
							}


							neiboursCnt++;
							if (MAX_NEIGHBOURS>0 && neiboursCnt>=MAX_NEIGHBOURS)
								hotLoopExit = true;

						} //for (int k=0; k<PLAYERS_IN_GROUP; k++)
					} // if (conflictPosis[0]>j || (conflictPosis[0]<j && conflictPlayersTmp < PLAYERS_IN_GROUP) )

				} //for (int j=0; j<GROUPS_IN_WEEK; j++) {
				prevJOfConflictPos = i2;
				iterMtrxConflictIndecesLists++;

			} // while (iterInErrorList != errorList.end() )
		}
	} //for (int i=0; i<WEEKS; i++)
	if (TABLE_CHANGE_REGIME == 1) {
		iterTablesId = tablesIndecesForNeighboursGeneration.begin();
		int week = (*iterTablesId);
		tablesIndecesForNeighboursGeneration.pop_front();
		tablesIndecesForNeighboursGeneration.push_back(week);
	}
	delete [] conflictsCurrPlayerWithConflictPlayerGroup;
	delete [] JIndecesOfConflictGroups;
}

int* TabuSearch::ChooseBestVariant2(list<int*>& bestNonTabuNeighborhoodList, list<int*>& bestTabuNeighborhoodList, int often) {
	static int minConflicts2 = currConflicts;
	if (minConflicts2>currConflicts)
		minConflicts2 = currConflicts;

	list<int*>::iterator iterNonTabu = bestNonTabuNeighborhoodList.begin();
	list<int*>::iterator iterTabu = bestTabuNeighborhoodList.begin();
	list<int*>* neighbourList;
	list<int*>::iterator iterNeighbour;

	if (iterNonTabu == bestNonTabuNeighborhoodList.end()
			|| ( iterTabu != bestTabuNeighborhoodList.end() && (*iterTabu)[5]<(*iterNonTabu)[5]
			&& currConflicts+(*iterTabu)[5]<minConflicts  && currConflicts+(*iterTabu)[5]<minConflicts2 ) ) {
		neighbourList = &bestTabuNeighborhoodList;
		iterNeighbour = neighbourList->begin();
	}
	else {
		neighbourList = &bestNonTabuNeighborhoodList;
		iterNeighbour = neighbourList->begin();
	}


	int* tmpVar = NULL;
	if (often == -1)
		tmpVar = (*iterNeighbour);
	else {
		int frequency;
		if (often = 1)
			frequency = -1000;
		else
			frequency = currIteration+FREQUENCY_FOR_LAST_ITERATIONS+FREQUENCY_FOR_LAST_ITERATIONS; // big value

		while ( iterNeighbour != neighbourList->end()) {
			int* neighbour = (*iterNeighbour);
			int weekId = neighbour[0];
			int player1 = mtrx3Schedule[weekId][neighbour[1]][neighbour[2]];
			int player2 = mtrx3Schedule[weekId][neighbour[3]][neighbour[4]];

			int tmp =mtrx4Tabu[weekId][player1][player2][1]-lowFrequencyThreshould;
			int curFrequency = (tmp<0)?0:tmp;
			if ( (often==0 &&  curFrequency<frequency )
					|| (often==1 && curFrequency>frequency) ) {
				tmpVar = neighbour;
				frequency = curFrequency;
			}
			iterNeighbour++;
		}
	}

	int* bestVar = new int[6];
		for (int i=0; i<6; i++)
			bestVar[i] = tmpVar[i];

	return bestVar;
}

void TabuSearch::snapshot() {
	if (mtrx3BestSchedule != NULL)
		Lib::deleteMatrix3(mtrx3BestSchedule, WEEKS, GROUPS_IN_WEEK);
	mtrx3BestSchedule = Lib::makeCopyOfMtrx3(mtrx3Schedule, WEEKS, GROUPS_IN_WEEK, PLAYERS_IN_GROUP);
	minConflicts = currConflicts;
	bestIteration = currIteration;
}

// Correct arrConflictIndeces and mtrx3ConflictIndeces after changing count of games in function void TabuSearch::applyChanges(int* neighbour);
void TabuSearch::updateConflictStatus(int player1, int player2, bool addConflict, int exceptWeek) {
	int players1Pos;
	int players2Pos;
	bool hotExitLoopJK;
	bool hotExitLoopI = false;
	int CountDownMaxPairCnt = addConflict?mtrxGames[player1][player2]-1:mtrxGames[player1][player2];
	for (int i=0; i<WEEKS && !hotExitLoopI; i++) {
		if (i == exceptWeek) continue;
		hotExitLoopJK = false;
		for (int j=0; j<GROUPS_IN_WEEK && !hotExitLoopJK; j++) {
			players1Pos = -1;
			players2Pos = -1;
			for (int k=0; k<PLAYERS_IN_GROUP && !hotExitLoopJK; k++) {
				if (mtrx3Schedule[i][j][k] == player1)
					players1Pos = k;
				else if (mtrx3Schedule[i][j][k] == player2)
						players2Pos = k;
				if (players1Pos>=0 && players2Pos>=0) {
					if (addConflict) {
						if (mtrx3ConflictIndeces[i][j][players1Pos] == 0)
							mtrxConflictIndecesLists[i][j].push_back(players1Pos);
						if (mtrx3ConflictIndeces[i][j][players2Pos] == 0)
							mtrxConflictIndecesLists[i][j].push_back(players2Pos);
						if (mtrxGames[player1][player2] == 2) {
							mtrx3ConflictIndeces[i][j][players1Pos]++;
							mtrx3ConflictIndeces[i][j][players2Pos]++;
						}
					}
					else {
						if (mtrxGames[player1][player2] == 1) {
							mtrx3ConflictIndeces[i][j][players1Pos]--;
							mtrx3ConflictIndeces[i][j][players2Pos]--;
						}
						if (mtrx3ConflictIndeces[i][j][players1Pos] == 0)
							mtrxConflictIndecesLists[i][j].remove(players1Pos);
						if (mtrx3ConflictIndeces[i][j][players2Pos] == 0)
							mtrxConflictIndecesLists[i][j].remove(players2Pos);
					}
					hotExitLoopJK = true;
					CountDownMaxPairCnt--;
					if (CountDownMaxPairCnt == 0)
						hotExitLoopI = true;
				}
			}
		}
	}
}

void TabuSearch::applyChanges(int* neighbour) {
	int player1 = mtrx3Schedule[neighbour[0]][neighbour[1]][neighbour[2]];
	int player2 = mtrx3Schedule[neighbour[0]][neighbour[3]][neighbour[4]];

	mtrxConflictIndecesLists[neighbour[0]][neighbour[1]].clear();
	mtrxConflictIndecesLists[neighbour[0]][neighbour[3]].clear();
	mtrx3ConflictIndeces[neighbour[0]][neighbour[1]][neighbour[2]] = 0;
	mtrx3ConflictIndeces[neighbour[0]][neighbour[3]][neighbour[4]] = 0;
	int playerK;
	int gamesPlayer1WithPlayerK;
	int gamesPlayer2WithPlayerK;
	for (int k=0; k<PLAYERS_IN_GROUP; k++) {
		if (k != neighbour[2]) {
			playerK = mtrx3Schedule[neighbour[0]][neighbour[1]][k];
			gamesPlayer1WithPlayerK = (mtrxGames[player1][playerK]>1)?1:0;
			gamesPlayer2WithPlayerK = (mtrxGames[player2][playerK]>0)?1:0;

			mtrx3ConflictIndeces[neighbour[0]][neighbour[1]][k] += gamesPlayer2WithPlayerK - gamesPlayer1WithPlayerK;
			mtrx3ConflictIndeces[neighbour[0]][neighbour[1]][neighbour[2]]
			      += gamesPlayer2WithPlayerK;
			if (mtrx3ConflictIndeces[neighbour[0]][neighbour[1]][k] > 0)
				mtrxConflictIndecesLists[neighbour[0]][neighbour[1]].push_back(k);

			mtrxGames[player1][playerK]--;
			mtrxGames[playerK][player1]--;
			mtrxGames[player2][playerK]++;
			mtrxGames[playerK][player2]++;

			if (mtrxGames[player1][playerK] > 0)
				updateConflictStatus(player1, playerK, false, neighbour[0]);
			if (mtrxGames[player2][playerK] > 1)
				updateConflictStatus(player2, playerK, true, neighbour[0]);
		}
		if (k != neighbour[4]) {
			playerK = mtrx3Schedule[neighbour[0]][neighbour[3]][k];
			gamesPlayer1WithPlayerK = (mtrxGames[player1][playerK]>0)?1:0;
			gamesPlayer2WithPlayerK = (mtrxGames[player2][playerK]>1)?1:0;
			mtrx3ConflictIndeces[neighbour[0]][neighbour[3]][k] += gamesPlayer1WithPlayerK - gamesPlayer2WithPlayerK;
			mtrx3ConflictIndeces[neighbour[0]][neighbour[3]][neighbour[4]]
				  += gamesPlayer1WithPlayerK;
			if (mtrx3ConflictIndeces[neighbour[0]][neighbour[3]][k] > 0)
				mtrxConflictIndecesLists[neighbour[0]][neighbour[3]].push_back(k);

			mtrxGames[player2][playerK]--;
			mtrxGames[playerK][player2]--;
			mtrxGames[player1][playerK]++;
			mtrxGames[playerK][player1]++;

			if (mtrxGames[player2][playerK] > 0)
				updateConflictStatus(player2, playerK, false, neighbour[0]);
			if (mtrxGames[player1][playerK] > 1)
				updateConflictStatus(player1, playerK, true, neighbour[0]);
		}
	}
	if (mtrx3ConflictIndeces[neighbour[0]][neighbour[1]][neighbour[2]] > 0)
		mtrxConflictIndecesLists[neighbour[0]][neighbour[1]].push_back(neighbour[2]);
	if (mtrx3ConflictIndeces[neighbour[0]][neighbour[3]][neighbour[4]] > 0)
		mtrxConflictIndecesLists[neighbour[0]][neighbour[3]].push_back(neighbour[4]);

	int rndValue;
	if (MAX_PLYAER_PENALTY != MIN_PLAYER_PENALTY)
		rndValue = rand() % ( MAX_PLYAER_PENALTY - MIN_PLAYER_PENALTY + 1 ) + MIN_PLAYER_PENALTY;
	else
		rndValue = MAX_PLYAER_PENALTY;

	mtrx4Tabu[neighbour[0]][player1][player2][0] = currIteration + rndValue + 1;
	mtrx4Tabu[neighbour[0]][player2][player1][0] = currIteration + rndValue + 1;

	int tmpFrq=mtrx4Tabu[neighbour[0]][player1][player2][1]-lowFrequencyThreshould;
	tmpFrq = (tmpFrq<=0)?lowFrequencyThreshould+1:mtrx4Tabu[neighbour[0]][player1][player2][1]+1;
	mtrx4Tabu[neighbour[0]][player1][player2][1] = tmpFrq;
	mtrx4Tabu[neighbour[0]][player2][player1][1] = tmpFrq;



	mtrx3Schedule[neighbour[0]][neighbour[1]][neighbour[2]] = player2;
	mtrx3Schedule[neighbour[0]][neighbour[3]][neighbour[4]] = player1;
	currConflicts += neighbour[5];

}

void TabuSearch::rndPlayersChangeForHardPerturbation() {
	int rndI = (rand() % WEEKS);
	int rndJ1 = (rand() % GROUPS_IN_WEEK);
	int rndK1 = (rand() % PLAYERS_IN_GROUP);
	int rndJ2 = (rand() % GROUPS_IN_WEEK);
	int rndK2 = (rand() % PLAYERS_IN_GROUP);
	if (rndJ1 == rndJ2) {
		if (rndJ1<GROUPS_IN_WEEK-1)
			rndJ2 = rndJ1+1;
		else
			rndJ2 = rndJ1-1;
	}
	int tmpPlayer = mtrx3Schedule[rndI][rndJ1][rndK1];
	mtrx3Schedule[rndI][rndJ1][rndK1] = mtrx3Schedule[rndI][rndJ2][rndK2];
	mtrx3Schedule[rndI][rndJ2][rndK2] = tmpPlayer;
}

void TabuSearch::hardPerturbation() {
	if (GROUPS_IN_WEEK<2)
			return;

		rndPlayersChangeForHardPerturbation();

		Lib::deleteMatrix3(mtrx3Schedule, WEEKS, GROUPS_IN_WEEK);
		mtrx3Schedule = Lib::makeCopyOfMtrx3(mtrx3BestSchedule, WEEKS, GROUPS_IN_WEEK, PLAYERS_IN_GROUP);

	tablesIndecesForNeighboursGeneration.clear();
		for (int i=0; i<WEEKS; i++) {
			tablesIndecesForNeighboursGeneration.push_back(i);
			for (int j=0; j<GROUPS_IN_WEEK; j++) {
				mtrxConflictIndecesLists[i][j].clear();
				for (int k=0; k<PLAYERS_IN_GROUP; k++) {
					mtrx3ConflictIndeces[i][j][k] = 0; // there is not conflict in this position
				}
			}
		}

		for (int i=0; i<playersCnt; i++) {
			for (int j=0; j<playersCnt; j++) {
				if (i==j)
					mtrxGames[i][j] = -1000000; // isn't allowedh
				else
					mtrxGames[i][j] = 0;
			}
		}

		for (int i=0; i<WEEKS; i++) {
			for (int j=0; j<playersCnt; j++) {
				for (int k=0; k<playersCnt; k++) {
					if (j != k) {
						mtrx4Tabu[i][j][k][0] = 0; // penalty
						mtrx4Tabu[i][j][k][1] = 0; // frequency
					}
					else
						mtrx4Tabu[i][j][k] = NULL;
				}
			}
		}

	lowFrequencyThreshould = 0;

	applyFastSolution();
}

void TabuSearch::softPerturbation() {
	int rndI = (rand() % WEEKS);
	int rndJ1 = (rand() % GROUPS_IN_WEEK);
	int rndK1 = (rand() % PLAYERS_IN_GROUP);
	int rndJ2 = (rand() % GROUPS_IN_WEEK);
	int rndK2 = (rand() % PLAYERS_IN_GROUP);
	if (rndJ1 == rndJ2) {
		if (rndJ1<GROUPS_IN_WEEK-1)
			rndJ2 = rndJ1+1;
		else
			rndJ2 = rndJ1-1;
	}

	int* nb = new int[6];
	nb[0] = rndI;
	nb[1] = rndJ1;
	nb[2] = rndK1;
	nb[3] = rndJ2;
	nb[4] = rndK2;

	int p1=0;
	int p2=0;
	int player1=mtrx3Schedule[rndI][rndJ1][rndK1];
	int player2=mtrx3Schedule[rndI][rndJ2][rndK2];
	for ( int kk=0; kk<PLAYERS_IN_GROUP; kk++) {
		int playerK1=mtrx3Schedule[rndI][rndJ1][kk];
		int playerK2=mtrx3Schedule[rndI][rndJ2][kk];
		if (kk != rndK2 && mtrxGames[player1][playerK2]>0)
			p1++;
		if (kk != rndK1 && mtrxGames[player2][playerK1]>0)
			p2++;
	}
	nb[5] = p1+p2 - mtrx3ConflictIndeces[rndI][rndJ1][rndK1]- mtrx3ConflictIndeces[rndI][rndJ2][rndK2];
	applyChanges(nb);
}

void TabuSearch::softPerturbations() {
	for (int i = 0; i<WEEKS-1; i++) {
		softPerturbation();
	}
}

int TabuSearch::ScheduleIt() {
	if (!wasInit) {
		status = -3; return status; // there was not initialisation
	}

	int counterOfIterationsForFrequency = FREQUENCY_FOR_LAST_ITERATIONS;
	status = 0; // solution is found
	currIteration=0;
	hotScheduleStop = false;
	list<int*> neighborhoodList;
	list<int*> bestNonTabuNeighborhoodList;
	list<int*> bestTabuNeighborhoodList;
	int howLongThereisNoProgress=0;
	int prevDelta = 1000000000;
	int restartCountDown = MAX_SOFT_PERTURBATIONS;
	srand ( time(NULL) ); // initialize random seed.
	while ( (MAX_ITERATION<0 || (MAX_ITERATION>=0 &&  currIteration<MAX_ITERATION)) && !hotScheduleStop && (currConflicts > 0) ) {
		currIteration++;
		neighborhoodList.clear();
		bestNonTabuNeighborhoodList.clear();
		bestTabuNeighborhoodList.clear();

		counterOfIterationsForFrequency--;
		if (counterOfIterationsForFrequency<=0) {
			lowFrequencyThreshould = currIteration;
			counterOfIterationsForFrequency = FREQUENCY_FOR_LAST_ITERATIONS;
		}

		GenerateNeighbor2(neighborhoodList, bestNonTabuNeighborhoodList, bestTabuNeighborhoodList);
		int* bestVar = ChooseBestVariant2(bestNonTabuNeighborhoodList, bestTabuNeighborhoodList, CHOOSE_OFTEN_PLYAER_SWAPS);
		Lib::deleteValueofPointersToArrInList(neighborhoodList);
		if (bestVar[5]>=0 && currConflicts < minConflicts )
			snapshot();
		applyChanges(bestVar);


		//if (prevDelta <= 0 && prevDelta <= bestVar[5]) {
		//	howLongThereisNoProgress++;
		//	if (MAX_WAITING_OF_PROGRESS > 0 && howLongThereisNoProgress>MAX_WAITING_OF_PROGRESS) {
		////		hardPerturbation();
		//		softPerturbations();
		//
		//		howLongThereisNoProgress=0;
		//	}
		//}

		if (currConflicts >= minConflicts) {
			howLongThereisNoProgress++;
			if (MAX_WAITING_OF_PROGRESS > 0 && howLongThereisNoProgress>MAX_WAITING_OF_PROGRESS) {
				if (restartCountDown > 0) {
					softPerturbations();
					restartCountDown--;
				}
				else {
					hardPerturbation();
					restartCountDown = MAX_SOFT_PERTURBATIONS;
				}
				howLongThereisNoProgress=0;
			}
		}
				prevDelta = bestVar[5];
				delete [] bestVar;
	}

	if (currConflicts < minConflicts)
		snapshot();

	if (minConflicts>0)
		status = -2; // solution was not found. Algorithm is stopped

	return status;
}

string TabuSearch::getParametersAsString() {
	string params = Search::getParametersAsString();
	std::stringstream out;
	out<<"START_INIT_ALG = "<<START_INIT_ALG<< "  (0 - don't use EXHAUSTIVE_SEARCH algorithm, 1 - use EXHAUSTIVE_SEARCH algorithm)" <<endl;
	out<<"FAST_SOLUTION_IN_MkSec = "<<FAST_SOLUTION_IN_MkSec<< "  (limit of time for EXHAUSTIVE_SEARCH algorithm, if START_INIT_ALG = 1, -1 - not set)" <<endl;
	out<<"FAST_SOLUTION_MAX_ITERATION = "<<FAST_SOLUTION_MAX_ITERATION<< "  (limit of iterations for EXHAUSTIVE_SEARCH algorithm, if START_INIT_ALG = 1, -1 - not set)" <<endl;
	out<<"MIN_PLAYER_PENALTY = "<<MIN_PLAYER_PENALTY<< "  (the minimum time a pair of golfers stays in the tabu list)" <<endl;
	out<<"MAX_PLYAER_PENALTY = "<<MAX_PLYAER_PENALTY<< "  (the maximum time a pair of golfers stays in the tabu list)" <<endl;
	out<<"MAX_NEIGHBOURS = "<<MAX_NEIGHBOURS<< "  (maximum amount of neighbourhood solutions, -1 - not set)" <<endl;
	out<<"TABLE_CHANGE_REGIME = "<<TABLE_CHANGE_REGIME << "  (0 - don't change table's order, 1 - change table order every iteration, first table becomes to be the last one)" <<endl;
	out<<"MAX_WAITING_OF_PROGRESS = "<<MAX_WAITING_OF_PROGRESS<< "  (maximum amount of iterations without progress, after that perturbation is invoked)" <<endl;
	out<<"MAX_SOFT_PERTURBATIONS = "<<MAX_SOFT_PERTURBATIONS<< "  (maximum perturbations after which tabu search starts again from last solution)" <<endl;
	out<<"FREQUENCY_FOR_LAST_ITERATIONS = "<<FREQUENCY_FOR_LAST_ITERATIONS<< "  (quantity of iteration after which information about frequency for every swap are deleted)" <<endl;
	out<<"CHOOSE_OFTEN_PLYAER_SWAPS = "<<CHOOSE_OFTEN_PLYAER_SWAPS<<"  (-1 - choose first best swap, 0 - choose more rarely chosen swap from the best, 1 - choose more often chosen swap from the best)" << endl;

	params.append(out.str());
	return params;
}
